#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<vector>
#include<queue>
using namespace std;
class Solution {
    unordered_map<char, unordered_set<char>> as;
    unordered_map<char, int> aq;
    bool check;
public:
    string alienOrder(vector<string>& words) {
        for (auto& e : words)
        {
            for (auto& r : e)
            {
                aq[r] = 0;
            }
        }
        int n = words.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if (check)
                    return "";
            }
        }
        queue<char> qw;
        string ret;
        for (auto& [a, b] : aq)
        {
            if (b == 0)
                qw.push(a);
        }
        while (qw.size())
        {
            char w = qw.front();
            qw.pop();
            ret += w;
            for (auto& e : as[w])
            {
                if (--aq[e] == 0)
                    qw.push(e);
            }
        }
        for (auto& [a, b] : aq)
        {
            if (b != 0)
            {
                return "";
            }
        }
        return ret;
    }
    void add(string& a, string& b)
    {
        int n = min(a.size(), b.size());
        int i = 0;
        for (; i < n; i++)
        {
            if (a[i] != b[i])
            {
                char c = a[i];
                char d = b[i];
                if (!as.count(c) || !as[c].count(d))
                {
                    as[c].insert(d);
                    aq[d]++;
                }
                break;
            }
        }
        if (i < a.size() && i == b.size())
            check = true;
    }
};